;; Copyright (c) [2022] [bobwxc]
;; This file is licensed under Mulan PubL v2.
;; You can use this software according to the terms and conditions of the Mulan PubL v2.
;; You may obtain a copy of Mulan PubL v2 at:
;;          http://license.coscl.org.cn/MulanPubL-2.0
;; THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
;; EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
;; MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
;; See the Mulan PubL v2 for more details.

(in-package #:cl-mdb)

(defun init-index-array()
  (make-array 65536 ;; 2^16, 2 bytes
              :element-type 'list
              :initial-element nil))

(defun hash-key(key)
  (declare (string key))
  (let* ((na (loop for i from 0 to (- (length key) 1)
                   collect(char-code (char key i))))
         (nl (reduce #'(lambda (x y) ;; handle unicode char
                         (append x
                                 (let ((i y)
                                       (x '()))
                                   (loop until(= i 0)
                                         do(progn
                                             (setf x (append x
                                                             (list (mod i #16r100000000))))
                                             (setf i (ash i -8))))
                                   (reverse x)))) ;; big endian storage
                     (cons '() na))))
    (mr3:murmur3-x64-128 nl 0)))

(defun insert-before-greater (lst keyhash ptr)
  (declare (list lst)
           (number keyhash))
  (cond
   ((equal lst nil) (cons (list keyhash ptr) lst))
   ((equal (car lst) nil) (cons (car lst) (insert-before-greater (cdr lst) keyhash ptr)))
   ((> (caar lst) keyhash) (cons (list keyhash ptr) lst))
   (t (cons (car lst) (insert-before-greater (cdr lst) keyhash ptr)))
   ))
;;   (if (or (equal lst nil) (> (caar lst) keyhash)) ;; =nil first, nil can't do > compare
;;       (cons (list keyhash ptr) lst) ;; (keyhash . ptr)
;;     (cons (car lst) (insert-before-greater (cdr lst) keyhash ptr))
;;     ))

;; (format t "~X" (insert-before-greater '(1 2 3 5 5) 4 32))

(defun insert-key (key-array key ptr)
  (declare (array key-array)
           (string key))
  (let* ((keyhash (hash-key key))
         (head (ash keyhash -112)) ;; first 16 bits
         (r (insert-before-greater (aref key-array head) keyhash ptr)))
    (setf (aref key-array head) r)
    key-array))

;; (insert-key (init-index-array) "abc")

(defun select-key (key-array key)
  (let* ((keyhash (hash-key key))
         (head (ash keyhash -112))
         )
    (dolist (i (aref key-array head))
      (when (= (car i) keyhash)
        (return i))) ;; return '(keyhash ptr) or nil
    ))

;; (print (select-key (insert-key (init-index-array) "abc" 123) "abc"))

(defun gc-index (key-array gc-key-list)
  (let* ((kl (mapcar #'(lambda (k) (cons (hash-key k) k)) gc-key-list))
         (skl (sort kl #'(lambda (a b) (< (car a) (car b))))))
    (dolist (i skl)
      (setf (aref key-array (ash (car i) -112))
            (remove nil
                    (mapcar #'(lambda (x) (if (= (car x) (car i))
                                              nil
                                            x))
                            (aref key-array (ash (car i) -112))))))
    key-array))

(defun re-index (root-list)
  (dolist (i (cadr root-list))
    (setf (car root-list) (insert-index (car root-list) (row-original-key i) i)))
  root-list)

(defun insert-index (key-array key ptr)
  (insert-key key-array key ptr))

(defun select-index (key-array key)
  (select-key key-array key))

